/*
 * @lc app=leetcode id=34 lang=cpp
 *
 * [34] Find First and Last Position of Element in Sorted Array
 */
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret;
        int len = nums.size();
        if (len < 1) {
            return {-1,-1};
        }

        int i=0, j=len-1, mid;
        while(i<=j) {
            mid = (i+j)/2;
            if (nums[mid] == target) {
                return searchRangeAround(nums, target, mid);
            } else if (nums[mid] > target) {
                j = mid-1;
            } else {
                i = mid+1;
            }
        }
        return {-1,-1};
    }

    vector<int> searchRangeAround(vector<int>& nums, int target, int pos) {
        int len = nums.size();
        
        vector<int> ret;
        int l=pos, r=pos;
        int i=0, j=pos, mid;
        while(i<j) {
            mid = (i+j)/2;
            if (nums[mid] == target) {
                l = mid;
                if (mid == 0 || (mid>0 && nums[mid-1]!=target)) {
                    break;
                } else {
                    j = j-1;
                }
            } else if (nums[mid] < target) {
                i = i+1;
            }
        }

        i=pos;
        j=len;
        while(i<j) {
            mid = (i+j)/2;
            if (nums[mid] == target) {
                r = mid;
                if (mid == len-1 || (mid<len-1 && nums[mid+1]!=target)) {
                    break;
                } else {
                    i = i+1;
                }
            } else if (nums[mid] > target) {
                j=j-1;
            }
        }
        return {l, r};
    }
};

